package mao.leetcode.offer;

import mao.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Totoro
 * @date 2020/8/26
 * @explain:
 */
public class offer26 {
}
//通过递归，完成。
class Solution2 {
    TreeNode B;
    boolean flag;
    boolean res = false;
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (null == B || null == A) return false;
        this.B = B;
        res = false;
        helper(A,B);
        return res;
    }

    public void helper(TreeNode A,TreeNode B){
        if (null == A || res) return ;
        if (A.val == B.val){
            flag = true;
            verify(A,B);
            if (flag){
                res = true;
                return;
            }
        }
        helper(A.left,B);
        // list.add(A.val);
        helper(A.right,B);
    }

    public void verify(TreeNode A,TreeNode B){
        if (!flag) return;
        if (null == B) return;
        if (null == A || A.val != B.val) {
            flag = false;
            return;
        }
        verify(A.left,B.left);
        verify(A.right,B.right);
    }
}

// 通过中序判断，有相同的值,会出错。
class Solution {
    // TreeNode B;
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (null == B || null == A) return false;
        List<Integer> listA = new ArrayList<>();
        List<Integer> listB = new ArrayList<>();
        helper(A,listA);
        helper(B,listB);
        // boolean flag;
        for(int i=0;i<listA.size();i++){
            if (listA.get(i) == listB.get(0)){
                if (listA.size()-i < listB.size()) return false;
                //flag = true;
                int k=0;
                for(;k<listB.size();k++){
                    if (listB.get(k) != listA.get(i+k)){
                        break;
                    }
                }
                if (k == listB.size()) return true;
            }
        }
        return false;
    }

    public void helper(TreeNode A,List list){
        if (null == A) return ;
        helper(A.left,list);
        list.add(A.val);
        helper(A.right,list);
    }
}